package btree;

public class MyBtree2 {

    static class BTRNode {
        public int[] keys;
        public BTRNode[] subs;
        public int usedSize;
        public BTRNode parent;

        public BTRNode() {
            this.keys = new int[M];
            this.subs = new BTRNode[M + 1];
            this.parent = null;
            this.usedSize = 0;
        }
    }
        public static final int M = 3;
        public BTRNode root;
        public boolean insert(int key) {
            if(root == null) {
                // 首次插入，直接实例化即可
                root = new BTRNode();
                root.keys[0] = key;
                root.usedSize++;
                return true;
            }
            // 不是首次插入，需要遍历查看key是否存在
            Pair<BTRNode,Integer> ret = find(key);
            if(ret.getVal() != -1) {
                // 不等于-1就表明key 在cur的key的keys的i下下标
                return true;
                // 当前节点已存在
            }
            // 不存在，开始插入
            BTRNode parent = ret.getKey();
            int index = parent.usedSize - 1;
            for(;index >= 0;index--) {
                if(parent.keys[index] > key) {
                    parent.keys[index + 1] = parent.keys[index];
                }else {
                    break;
                }
            }
            parent.keys[index + 1] = key;
            parent.usedSize++;
            // 插入结束
            if(parent.usedSize < M) {
                return true;
            }else {
                // 分裂
                split(parent);
                return true;
            }
        }

        private void split(BTRNode cur) {
            BTRNode newNode = new BTRNode();// 新建立的兄弟节点
            int mid = cur.usedSize/2; // 当前要分裂的中间的数组下标
            int i = mid+1; // 要分裂的节点的下标
            int j = 0;// 新建立的数组的下标
            for(;i < cur.usedSize;i++) {
                newNode.keys[j] = cur.keys[i]; // 拷贝key
                newNode.subs[j] = cur.subs[i]; // 拷贝还是
                if(newNode.subs[j] != null) {
                    // 如果拷贝过来的孩子不是空，那就需要改变孩子的parent
                    newNode.subs[j].parent = newNode;
                }
                j++;
            }
            // 到这里key已经全部拷贝完毕，但是还差一个孩子
            // 多拷贝一个孩子
            newNode.subs[j] = cur.subs[i];
            if(newNode.subs[j] != null) {
                newNode.subs[j].parent = newNode;
            }

            // 接下来更改cur 和 newNode 的usedSize
            newNode.usedSize = j; // j 代表的是移动了多少个key
            cur.usedSize = cur.usedSize - j - 1;
            // 这里cur的usedsize - j（这里代表的是被移到兄弟的孩子数量） - 1（这个代表的是中间被提走的keys[mid]）
            // 接下来开始提cur[mid]
            BTRNode parent = cur.parent; // cur的父亲节点
            int midVal = cur.keys[mid]; // midVal 是要往上提的值

            if(parent == null) {
                // 当前要分裂的是根节点
                root = new BTRNode();
                root.keys[0] = cur.keys[mid];
                root.subs[0] = cur;
                cur.parent = root;
                root.subs[1] = newNode;
                newNode.parent = root;
                root.usedSize = 1;
                return;
            }

            int index = parent.usedSize - 1;
            for(;index >= 0;index--) {
                if(parent.keys[index] > midVal) {
                    parent.keys[index + 1] = parent.keys[index];
                    parent.subs[index + 2] = parent.subs[index + 1];
                }else {
                    break;
                }
            }
            // index 到0 或者到到达了要插入midVal的位置
            parent.subs[index + 2] = newNode;
            parent.keys[index + 1] = midVal;
            parent.usedSize++;

            if(parent.usedSize >= M) {
                // 还不满足条件，继续递归
                split(parent);
            }
        }

        private Pair<BTRNode,Integer> find(int key) {
            BTRNode cur = root;
            BTRNode parent = null;
            while(cur != null) {
                int i = 0;
                while(i < cur.usedSize) {
                    if(cur.keys[i] > key) {
                        break;
                    }else if(cur.keys[i] < key) {
                        i++;
                    }else {
                        // 当前key已经在B树内存在了，返回cur 和 i下标
                        return new Pair<>(cur,i);
                    }
                }
                parent = cur;
                cur = cur.subs[i];
            }
            // 当前树没有存储key节点，返回父类和-1去插入节点
            return new Pair<>(parent,-1);
        }

        public void inorder(BTRNode root){
            if(root == null)
                return;
            for(int i = 0; i < root.usedSize; ++i){
                inorder(root.subs[i]);
                System.out.println(root.keys[i]);
            }
            inorder(root.subs[root.usedSize]);
        }
}
